﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

// http://blog.csdn.net/clariones/article/details/1396880
// http://blog.csdn.net/clariones/article/details/1412394
// http://www.blogjava.net/phyeas/archive/2009/01/10/250807.html

namespace TextDiffAlgoCs
{
    public class TextComparer
    {
        public class TPoint
        {
            public int x;
            public int y;

            public TPoint(int x, int y)
            {
                this.x = x;
                this.y = y;
            }
        }

        protected static int GetV(int[][] arr, int i, int j)
        {
            if (i >= arr.Length || j >= arr[i].Length)
            {
                return 0;
            }
            return arr[i][j];
        }

        protected static int[][] GetMinStepArr(int[][] miarr, bool[][] barr)
        {
            int[][] iarr = new int[miarr.Length][];
            for (int i = 0; i < iarr.Length; i++)
            {
                iarr[i] = new int[miarr[i].Length];
            }

            for (int i = iarr.Length - 1; i >= 0; i--)
            {
                for (int j = iarr[i].Length - 1; j >= 0; j--)
                {
                    if (barr[i][j])
                    {
                        iarr[i][j] = GetV(iarr, i + 1, j + 1) + 1;
                    }
                    else if (GetV(miarr, i, j + 1) >= GetV(miarr, i + 1, j))
                    {
                        iarr[i][j] = GetV(iarr, i, j + 1);
                    }
                    else
                    {
                        iarr[i][j] = GetV(iarr, i + 1, j) + 1;
                    }
                }
            }

            return iarr;
        }

        protected static int[][] GetStepPathArr(bool[][] barr)
        {
            int[][] iarr = new int[barr.Length][];
            for (int i = 0; i < iarr.Length; i++)
            {
                iarr[i] = new int[barr[i].Length];
            }

            for (int i = barr.Length - 1; i >= 0; i--)
            {
                for (int j = barr[i].Length - 1; j >= 0; j--)
                {
                    int v_i_j = barr[i][j] ? 1 : 0;
                    int n_i_1_j_1 = ((i + 1 >= iarr.Length) || (j + 1 >= iarr[i].Length)) ? 0 : iarr[i + 1][j + 1];
                    int n_i_1_j = (i + 1 >= iarr.Length) ? 0 : iarr[i + 1][j];
                    int n_i_j_1 = (j + 1 >= iarr[i].Length) ? 0 : iarr[i][j + 1];
                    int v_n_1_1 = v_i_j + n_i_1_j_1;
                    iarr[i][j] = (v_n_1_1 > n_i_1_j) ? ((v_n_1_1 > n_i_j_1) ? v_n_1_1 : n_i_j_1) : ((n_i_1_j > n_i_j_1) ? n_i_1_j : n_i_j_1);
                }
            }

            return iarr;
        }

        protected static bool[][] GetCompareBoolArray(string src, string cmp)
        {
            if (src.Equals("") || cmp.Equals(""))
            {
                throw new Exception("Must initialize the texts input.");
            }
            bool[][] comps = new bool[cmp.Length][];
            for (int i = 0; i < comps.Length; i++)
            {
                comps[i] = new bool[src.Length];
            }

            for (int i = 0; i < cmp.Length; i++)
            {
                for (int j = 0; j < src.Length; j++)
                {
                    comps[i][j] = (cmp[i] == src[j]);
                }
            }

            return comps;
        }

        protected static TPoint GetNext(TPoint p, int[][] miarr, int[][] diarr, bool[][] barr)
        {
            if (p.x >= barr.Length || p.y >= barr[p.x].Length)
            {
                return null;
            }
            if (barr[p.x][p.y])
            {
                return new TPoint(p.x + 1, p.y + 1);
            }

            List<TPoint> pts = new List<TPoint>();
            int Min = -1;

            for (int i = p.x; i < barr.Length; i++)
            {
                for (int j = p.y; j < barr[i].Length; j++)
                {
                    if (miarr[i][j] != miarr[p.x][p.y])
                    {
                        break;
                    }
                    if (barr[i][j] && miarr[i][j] == miarr[p.x][p.y])
                    {
                        if (Min == -1 || diarr[i][j] < Min)
                        {
                            Min = diarr[i][j];
                        }
                        pts.Add(new TPoint(i, j));
                    }
                }
            }

            if (pts.Count > 0)
            {
                for (int i = 0; i < pts.Count; i++)
                {
                    if (diarr[pts[i].x][pts[i].y] > Min)
                    {
                        pts.Remove(pts[i]);
                    }
                }
                if (pts.Count > 0)
                {
                    return pts[0];
                }
            }

            return null;
        }

        protected static List<TextDiff> CalcDiffs(TPoint startPoint, bool[][] barr, int[][] miarr, int[][] diarr)
        {
            if (startPoint == null)
            {
                return new List<TextDiff>();
            }
            List<TextDiff> diffs = new List<TextDiff>();

            if (startPoint.x != 0)
            {
                diffs.Add(new TextDiff(TextDiff.TYPE_INSERT, 0, startPoint.x));
            }
            if (startPoint.y != 0)
            {
                diffs.Add(new TextDiff(TextDiff.TYPE_DELETE, 0, startPoint.y));
            }
            TPoint next = GetNext(startPoint, miarr, diarr, barr);

            while (next != null)
            {
                if (!barr[startPoint.x][startPoint.y])
                {
                    if (startPoint.x != next.x)
                    {
                        diffs.Add(new TextDiff(TextDiff.TYPE_INSERT, startPoint.x, next.x - startPoint.x));
                    }
                    if (startPoint.y != next.y)
                    {
                        diffs.Add(new TextDiff(TextDiff.TYPE_DELETE, startPoint.y, next.y - startPoint.y));
                    }
                }
                startPoint = next;
                next = GetNext(startPoint, miarr, diarr, barr);
            }

            if (startPoint.x != barr.Length)
            {
                diffs.Add(new TextDiff(TextDiff.TYPE_INSERT, startPoint.x, barr.Length - startPoint.x));
            }
            if (startPoint.y != barr[0].Length)
            {
                diffs.Add(new TextDiff(TextDiff.TYPE_DELETE, startPoint.y, barr[0].Length - startPoint.y));
            }

            return diffs;
        }

        public static List<TextDiff> Compare(string src, string cmp)
        {
            if (src.Equals("") || cmp.Equals(""))
            {
                return new List<TextDiff>();
            }
            bool[][] barr = GetCompareBoolArray(src, cmp);
            int[][] miarr = GetStepPathArr(barr);
            int[][] diarr = GetMinStepArr(miarr, barr);
            List<TPoint> pts = new List<TPoint>();
            int maxJ = -1;

            for (int i = 0; i < barr.Length; i++)
            {
                int tmpMaxJ = -1;
                for (int j = 0; j < barr[i].Length; j++)
                {
                    if (j > maxJ && maxJ != -1)
                    {
                        break;
                    }
                    if (barr[i][j])
                    {
                        if (tmpMaxJ == -1)
                        {
                            tmpMaxJ = j;
                        }
                        pts.Add(new TPoint(i, j));
                    }
                }
                if (tmpMaxJ != -1)
                {
                    maxJ = tmpMaxJ;
                }
            }

            int Max = 0;
            int MinStep = -1;
            foreach (TPoint pt in pts)
            {
                if (miarr[pt.x][pt.y] > Max)
                {
                    Max = miarr[pt.x][pt.y];
                }
            }
            foreach (TPoint pt in pts)
            {
                if (MinStep == -1 || (miarr[pt.x][pt.y] >= Max && diarr[pt.x][pt.y] < MinStep))
                {
                    MinStep = diarr[pt.x][pt.y];
                }
            }

            for (int i = 0; i < pts.Count; i++)
            {
                if (miarr[pts[i].x][pts[i].y] < Max || diarr[pts[i].x][pts[i].y] > MinStep)
                {
                    pts.Remove(pts[i]);
                }
            }

            List<TextDiff> diffs = CalcDiffs((pts.Count >= 1 ? pts[0] : null), barr, miarr, diarr);

            return diffs;
        }

        public static List<TextDiff> Compare(string strSrc, string strCmp, ref double degree1, ref double degree2, ref double degreeMixed)
        {
            if (strSrc.Equals("") || strCmp.Equals(""))
            {
                return new List<TextDiff>();
            }

            string src = strSrc.Replace("\t", "");
            src = src.Replace("\n", "");
            src = src.Replace("\r", "");
            src = src.Replace(" ", "");

            string cmp = strCmp.Replace("\t", "");
            cmp = cmp.Replace("\n", "");
            cmp = cmp.Replace("\r", "");
            cmp = cmp.Replace(" ", "");

            int cnt1 = 0, cnt2 = 0;
            List<TextDiff> diffs = Compare(src, cmp);
            foreach (var td in diffs)
            {
                switch (td.getDiffType)
                {
                    case TextDiff.TYPE_DELETE:
                        cnt1 += td.getDiffLength;
                        break;
                    case TextDiff.TYPE_INSERT:
                        cnt2 += td.getDiffLength;
                        break;
                    default:
                        break;
                }
            }

            int len1 = src.Length, len2 = cmp.Length;

//             Console.WriteLine("cnt1: " + cnt1.ToString());
//             Console.WriteLine("cnt2: " + cnt2.ToString());
//             Console.WriteLine("len1: " + len1.ToString());
//             Console.WriteLine("len2: " + len2.ToString());

            degree1 = (double)(len1 - cnt1) / (double)len1;
            degree2 = (double)(len2 - cnt2) / (double)len2;
            degreeMixed = (double)(len1 + len2 - cnt1 - cnt2) / (double)(len1 + len2);

            return diffs;
        }

    }
}
